//
//  main.c
//  Test1
//
//  Created by Xavier on 2023/9/11.
//


//编程实现1 - 1/x + 1/×*x…•，要求用两种算法，分别为单循环和双循环
#include <stdio.h>
#include <math.h>
#include <time.h>

//x - 值 n - 最后的次方 （n+1）- 位数
//单循环
//思路：
//1、分析 假设看成数组
//2、开头的1下标就是0
//3、下标为奇数 - ，为偶数 +
double first(double x, int n) {
    double sum = 1;
    for (int i = 1; i <= n; i++) {
        sum += pow((-1), i) * 1/pow(x, i);
    }
    return sum;
}
//时间复杂度：O(N)
//空间复杂度：O(1)

double firstOther(double x, int n) {
    
}

//双循环
//思路：
//1、先把负的相加 -- 奇数负
//2、再把正的相加 -- 偶数正
//3、两个相加 得结果
double second(double x, int n) {
    double sum = 1;
    //求所有的负数
    double sumJi = 0;
    for (int i = 1; i <= n; i+=2) {
        sumJi += 1/pow(x, i);
    }
    //求所有的正数
    double sumOu = 0;
    for (int i = 2; i <= n; i+=2) {
        sumOu += 1/pow(x, i);
    }
    sum = sum - sumJi + sumOu;
    return sum;
}
//时间复杂度：O(2N)
//空间复杂度：O(1)

//思路：
//1、先不看+- 这是一个公比为1/x的等比数列
//2、把n分奇数 偶数分析
//3、利用Sn + (1/x)Sn
double third(double x, int n) {
    if (n % 2 == 0) {
        return ((1 + pow(x, n+1))) / ((1+x)*pow(x, n));
    }else {
        return ((pow(x, n+1) - 1)) / ((1+x)*pow(x, n));
    }
    return 0;
}
//时间复杂度：O(1)
//空间复杂度：O(1)

//递归
//思路：
//1、
//2、
//double forth(double x, int n) {
//    if (n == 1) return 1.0 - 1/x;
//    
//    if (n % 2 == 0) {
//        return pow(-1, n)*pow(x, n);
//    }else {
//        return pow(-1, n)*pow(x, n);
//    }
//    
//    if (n-1 > 0) {
//        return 1 + forth(x, n-1) + forth(x, n-2);
//    }
//    return 0;
//}





//int main() {
//    int x = 0;
//    int n = 0;
//    double dur1, dur2, dur3, dur4;
//    clock_t start,end;
//    scanf("%d", &x);
//    scanf("%d", &n);
//
//    //first
//    start = clock();
//    double num1 = first(x, n);
//    end = clock();
//    dur1 = (double)(end - start);
//
//    //second
//    start = clock();
//    double num2 = second(x, n);
//    end = clock();
//    dur2 = (double)(end - start);
//
//    //third
//    start = clock();
//    double num3 = third(x, n);
//    end = clock();
//    dur3 = (double)(end - start);
//

//
//
//
//    printf("first:%lf\n", num1);
//    printf("second:%f\n", num2);
//    printf("third:%f\n", num3);
//    //printf("forth:%f\n", num4);
//
//    printf("The First Use Time:%f\n",(dur1/CLOCKS_PER_SEC));
//    printf("The Second Use Time:%f\n",(dur2/CLOCKS_PER_SEC));
//    printf("The Third Use Time:%f\n",(dur3/CLOCKS_PER_SEC));
//    //printf("The Forth Use Time:%f\n",(dur3/CLOCKS_PER_SEC));
//
//    return 0;
//}
